# LeetCode 11、盛水最多的容器

# 一、题目描述

给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

# 二、题目解析

一开始,我们先去考虑相距最远的两个柱子所能容纳水的面积。

img

接下来去思考,我们去移动哪根柱子会更加合适?

这里我们需要注意一点:无论移动哪根柱子,柱子之间的宽度都是变小的

移动右边那根更高的柱子?

img

img

由于水面高度是由最短的柱子决定的,所以移动右边那根更高的柱子的时候,水面高度一定是不会增加,甚至有可能遇到更短的柱子而变小,而宽度有一定再减少,所以水的面积也一定减少

移动左边那根更短的柱子?

这时候,水的高度是不确定的,那么面积也是不确定的,有可能比之前更大,也有可能更小或者相等。

所以,我们可以得出一个结论:移动两根柱子之间更短的那根柱子,才有可能在宽度一定变小的情况下,找到一个更高的水面,从而使得面积有可能更大

那接下来这道题目的解法也就有了:

1、设置两个索引,分别指向容器的两侧,即索引 left 指向最左边的柱子,索引 right 指向最右边的柱子。

img

2、记录下此时的水的面积,可以定义为 res

3、观察需要向内移动哪根柱子

  • 1)如果移动较高的柱子,由于水的宽度在变小,而水的高度一定不会增加,所以最终水的面积不会超过之前记录的水的面积 res
  • 2)所以,只能移动较短的柱子,然后计算此时水的面积,再与之前记录的水的面积 res 进行比较,保存那个更大的值

4、再去判断应该向内移动哪根柱子

5、直到 leftright 相遇为止

# 三、参考代码

class Solution {
    public int maxArea(int[] height) {
       
       // 设置两个索引,分别指向容器的两侧

       // 索引 left 指向最左边的柱子
       int left = 0;

       // 索引 right 指向最右边的柱子
       int right = height.length - 1;

       // 设置一个变量用来保存当下水的最大面积
       int res = 0;

       // 移动 left 和 right,直到 left 和 right 相遇为止
       while(left < right){

           // 水的宽度是 right - left
           int width = right - left;

           // 水的高度由两根柱子最短的那根决定
           int h = Math.min(height[left],height[right]);

           // 计算此时水的面积
           int area = width * h;

           // 如果此时水的面积大于了我们之前保存的那个值,我们需要更新一下
           if(area >= res){
               // 更新 res 的值为 area,确保 res 一直都是最大的值
               res = area;
           }
        
           // 接下来去观察需要移动哪根柱子:必定是最短的那根柱子

           // 如果左边的柱子更短,那么向内移动左边的柱子,因为只有这样,才有可能找到一个更高的水面
           // 在宽度一定变小的情况下,水的面积才有可能增大
           if(height[left] < height[right]){
               // 向内移动左边的柱子
               left++;

           // 如果右边的柱子更短,那么向内移动右边的柱子,因为只有这样,才有可能找到一个更高的水面
           // 在宽度一定变小的情况下,水的面积才有可能增大
           }else{
               // 向内移动右边的柱子
               right--;
           }

       }
       
       // 最后返回最大的面积 res 即可
       return res;
    }
}
# https://www.algomooc.com/587.html
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 盛最多水的容器 ( LeetCode 11) : https://leetcode-cn.com/problems/container-with-most-water/
class Solution:
    def maxArea(self, height: List[int]) -> int:
       # 设置两个索引,分别指向容器的两侧

       # 索引 left 指向最左边的柱子
       left = 0

       # 索引 right 指向最右边的柱子
       right = len(height) - 1

       # 设置一个变量用来保存当下水的最大面积
       res = 0

       # 移动 left 和 right,直到 left 和 right 相遇为止
       while left < right :

           # 水的宽度是 right - left
           width = right - left

           # 水的高度由两根柱子最短的那根决定
           h = min(height[left],height[right])

           # 计算此时水的面积
           area = width * h

           # 如果此时水的面积大于了我们之前保存的那个值,我们需要更新一下
           if area >= res :
               # 更新 res 的值为 area,确保 res 一直都是最大的值
               res = area
           
           # 接下来去观察需要移动哪根柱子:必定是最短的那根柱子

           # 如果左边的柱子更短,那么向内移动左边的柱子,因为只有这样,才有可能找到一个更高的水面
           # 在宽度一定变小的情况下,水的面积才有可能增大
           if height[left] < height[right] :
               # 向内移动左边的柱子
               left += 1

           # 如果右边的柱子更短,那么向内移动右边的柱子,因为只有这样,才有可能找到一个更高的水面
           # 在宽度一定变小的情况下,水的面积才有可能增大
           else:
               # 向内移动右边的柱子
               right -= 1
            
       # 最后返回最大的面积 res 即可
       return res